// 207.课程表
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // <课程，入度值>
        Map<Integer, Integer> indegree = new HashMap<>();
        // <课程，指向的课程>
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

        // 初始化哈希表
        for (int i = 0; i < numCourses; i++) {
            indegree.put(i, 0);
        }

        // 构建入度表和邻接表
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[1];
            int preCourse = prerequisite[0];
            indegree.put(course, indegree.get(course) + 1);
            // 在key缺失时创建一个list插入到map中并添加课程
            adjacencyList.computeIfAbsent(preCourse, k -> new ArrayList<>()).add(course);
        }

        // 初始化队列，将入度为0的课程加入队列
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree.get(i) == 0) {
                queue.addLast(i);
            }
        }

        // 队列逐渐出队，表示学习该门课程
        while (!queue.isEmpty()) {
            int course = queue.removeFirst();

            // 获取当前课程指向的课程列表
            List<Integer> nextCourses = adjacencyList.getOrDefault(course, new ArrayList<>());

            // 调整入度，如果为0则入队
            for (int nextCourse : nextCourses) {
                indegree.put(nextCourse, indegree.get(nextCourse) - 1);
                if (indegree.get(nextCourse) == 0) {
                    queue.addLast(nextCourse);
                }
            }
        }

        // 检查所有课程的入度，如果有不为0的课程则存在环
        for (int inDegree : indegree.values()) {
            if (inDegree != 0) {
                return false;
            }
        }

        return true;
    }
}
